﻿//#include <iostream>
//#include <atomic>
//#include <mutex>
//#include <thread>
//#include <vector>   
//
//template<typename T>
//struct node {
//	T data;
//	node* next;
//	node(const T& data): data(data), next(nullptr){}
//};
//
//namespace lock_free{
//	template<typename T>
//	class stack {
//	public:
//		std::atomic<node<T>*> head = nullptr;
//		void push(const T& data){
//			node<T>* new_node = new node<T>(data);
//			// 将 head 的当前值放到 new_node->next 中 
//			new_node->next = head.load(std::memory_order_relaxed);
//			// 现在令 new_node 为新的 head ，但如果 head 不再是 
//			// 存储于 new_node->next 的值（某些其他线程必须在刚才插⼊结点） 
//			// 那么将新的 head 放到 new_node->next 中并再尝试 
//			while (!head.compare_exchange_weak(new_node->next, new_node,
//					std::memory_order_release,
//					std::memory_order_relaxed)); // 循环体为空 
//		}
//	};
//}
//
//namespace lock{
//	template<typename T>
//	class stack{
//	public:
//		node<T>* head = nullptr;
//		void push(const T& data){
//			node<T>* new_node = new node<T>(data);
//			new_node->next = head;
//			head = new_node;
//		}
//	};
//}
//
//
//
//int main(){
//	lock_free::stack<int> st1;
//	lock::stack<int> st2;
//	std::mutex mtx;
//	int n = 1000000;
//	auto lock_free_stack = [&st1, n] {
//		for (size_t i = 0; i < n; i++){
//			st1.push(i);
//		}
//	};
//	auto lock_stack = [&st2, &mtx, n] {
//		for (size_t i = 0; i < n; i++){
//			std::lock_guard<std::mutex> lock(mtx);
//			st2.push(i);
//		}
//	};
//
//	// 4个线程分别使⽤无锁⽅式和有锁⽅式插⼊n个数据到栈中对⽐性能 
//	size_t begin1 = clock();
//	std::vector<std::thread> threads1;
//	for (size_t i = 0; i < 4; i++){
//		threads1.emplace_back(lock_free_stack);
//	}
//	for (auto& th : threads1)th.join();
//	size_t end1 = clock();
//	std::cout << end1 - begin1 << std::endl;
//
//
//	size_t begin2 = clock();
//	std::vector<std::thread> threads2;
//	for (size_t i = 0; i < 4; i++){
//		threads2.emplace_back(lock_stack);
//	}
//	for (auto& th : threads2)th.join();
//	size_t end2 = clock();
//	std::cout << end2 - begin2 << std::endl;
//
//	return 0;
//}